class Solution {
    public static void main(String[] args) {
        String s = "mbadm" ;
        //          mbabm
        //          mbabm
        System.out.println(minInsertions(s));
    }
    public  static  int minInsertions(String s) {
       int len = s.length() ;
       char[] arr = s.toCharArray() ;
       boolean[][] f = new boolean[len][len];
       int[][] dp = new int[len][len] ; 
       for(int i=len-1; i >= 0; i --){
        for(int j=i ; j < len; j ++){
            if(arr[i] == arr[j]){
                f[i][j] = i+1< j ? f[i+1][j-1]: true ;
            }
        }
       }
       for(int i = len-1; i >=0 ; i --){
        for(int j= i ; j < len ; j ++){
            if(arr[i] == arr[j]){
           dp[i][j] = i+1<j ? (f[i+1][j-1]?0:dp[i+1][j-1])  : 0 ;
            }else{
             dp[i][j] = i+1 < j ? dp[i+1][j-1]+1     : 1 ;
            }
        }
       }
       return dp[0][len-1]; 
    }
}